package de.mpii.struct.trie;

import java.util.HashMap;
import java.util.Map;

public class TrieNode<T> {

	private final char keyChar;
	private final Trie<T> trie;
	private final TrieNode<T> parent;
	private final Map<Character, TrieNode<T>> children = new HashMap<Character, TrieNode<T>>();

	private T value;

	public TrieNode(Trie<T> trie, TrieNode<T> parent, char keyChar) {
		this.parent = parent;
		this.trie = trie;
		this.keyChar = keyChar;

		trie.increaseSize();
	}

	public void enumerate(StringBuilder sbuilder, int indent) {

		for (int i = 0; i < indent; i++)
			sbuilder.append(' ');

		sbuilder.append(this);
		sbuilder.append('\n');

		for (TrieNode<T> i : children.values()) {
			i.enumerate(sbuilder, indent + 4);
		}

	}

	/**
	 * 
	 * @param content
	 * @param startPos
	 * @return 0 if starting from this node, there is no such key as content,
	 *         otherwise, the length of the path from this node to the node
	 *         where we have no route to follow.
	 */
	public int extract(String content, int startPos) {
		if (isLeaf())
			return 0;

		if (!children.containsKey(content.charAt(startPos)))
			return -1;

		TrieNode<T> node = children.get(content.charAt(startPos));

		int endPos = node.extract(content, startPos + 1);

		/*
		 * we return -1 to offset the line (endPos + 1), such that in the end,
		 * if we cannot find a complete key (till a leaf) in Trie, we will
		 * return nothing.
		 */
		if (endPos == -1)
			return -1;

		return endPos + 1;
	}

	public T get(String key) {
		if (key.isEmpty())
			return value;

		char c = key.charAt(0);

		if (!children.containsKey(c))
			return null;

		return children.get(c).get(key.substring(1));
	}

	public String getKey() {
		if (isRoot())
			return "";

		String prefix = parent.getKey();

		return prefix + keyChar;
	}

	public T getValue() {
		return value;
	}

	public boolean isLeaf() {
		return children.isEmpty();
	}

	public boolean isRoot() {
		return parent == null;
	}

	public boolean put(String key, T value) {
		if (key.isEmpty()) {
			setValue(value);
			return true;
		}

		char c = key.charAt(0);

		TrieNode<T> node;

		if (children.containsKey(c))
			node = children.get(c);
		else {
			if (!isRoot() && isLeaf())
				return false;

			node = new TrieNode<T>(trie, this, c);
			children.put(c, node);
		}

		return node.put(key.substring(1), value);
	}

	public void setValue(T object) {
		this.value = object;
	}

	@Override
	public String toString() {
		return getKey() + ":" + value;
	}

}
